【题解】「Ynoi2018」天降之物 及其加强版「MtOI2019」手牵手走向明天 根号分治 / 序列分块 — Qiuly

最开始的想法是对序列分块，然后每个块维护一个 $\sqrt{n}\times \sqrt{n}$ 的矩阵表示这个块中颜色与颜色的距离，再维护每个颜色到左右端点的最短距离。

容易发现查询的时候很好查询，问题在于修改操作：要对每一个块进行处理，光是枚举块就要用掉 $O(\sqrt{n})$ 的时间，那就只能在一个块上留下 $O(1)$ 的时间来修改了，这似乎很难办。

深入思考一下，假设一个块中最开始有 $m$ 个颜色，那么修改 $x$ 为 $y$ ：

• $x$ 没有：那就不要管了。
• $y$ 没有，但 $x$ 有：记录一个颜色的实际值即可，修改的时候只需要修改指针。
• $x,y$ 都有：对于 $x,y$ 以外的 $m-2$ 个颜色，每一个颜色都需要进行 $O(1)$ 次修改，然后合并 $x,y$ 的颜色信息也是 $O(m)$ 的，总时间复杂度是 $O(m)$ ，并且操作完 $m$ 减少一。

那么一个块最多产生多少次操作？因为 $m$ 最大为 $\sqrt{n}$ ，所以一个块中的操作次数其实是 $O(n)$ 级别的。所以总操作次数就是 $O(n\sqrt{n})$ 。

这个做法再拓展拓展大概就能做”MtOI2019 手牵手走向明天”。

关于拓展：

• 区间修改：最主要的问题在于散块，整块可以按照上述方式做，散块的话最大的问题在于关于 $y$ 的距离怎么修改，因为做的是 $\min$ ，直接修改似乎不好办。于是你可以考虑到，先用 $O(\sqrt{n})$ 的代价将这一块的 $a_i$ 的实际值求出来，然后对于 $y$ 的相关信息直接求一遍，$x$ 的相关信息也直接求一遍，这一部分的复杂度是 $O(\sqrt{n})$ 的。
• 区间查询：区间内的可以直接查表，不同区间的可以扫过去，记录一下上一个位置（因为我们维护了一个颜色到块两边的距离）

这个时候大概就做完了，因为我没有实现，所以不放代码。

在这个做法中我最没有信心的就是” 区间修改” 部分，常数似乎不小 …

代码咕咕咕。

---

事实上，在第四分块中，我们完全可以避免这种复杂，卡常，码农的做法。

回忆一下之前的做法，对于每一个块中的每一种颜色维护了一个与同一块中其他颜色的最小距离。如果将这个做法换成全局的话，则需要 $O(n^2)$ 的空间。

同时可以发现，对于查询的话，复杂度跟 $x,y$ 的出现次数密切相关。

那么，能不能对出现次数超过 $\sqrt{n}$ 的不超过 $\sqrt{n}$ 个颜色，每一个颜色维护一个与其他颜色的最小距离呢？这样子的话空间花费就是 $O(n\sqrt{n})$ 的了。

这样的话查询时，如果 $x,y$ 有任意一方的出现次数超过 $\sqrt{n}$，就直接查表，否则用 $O(\sqrt{n})$ 的时间暴力求解。

接下来考虑合并颜色：

• 如果 $x,y$ 出现次数均小于 $\sqrt{n}$ ：暴力合并位置集合。如果合并完后出现次数大于 $\sqrt{n}$，则用 $O(n)$ 的时间构建距离数组。

• 如果 $x,y$ 出现次数均大于 $\sqrt{n}$ ：对颜色标号，用 $O(\sqrt{n})$ 更新其他颜色与 $x,y$ 的距离，然后暴力合并 $x,y$ 的距离数组，显然因为出现次数大于 $\sqrt{n}$ 的颜色数最多有 $\sqrt{n}$ 个，也就是最多出现 $\sqrt{n}$ 次这样的合并，因此复杂度时正确的。

• 如果 $x,y$ 出现次数有一方小于 $\sqrt{n}$，一方大于 $\sqrt{n}$ ：这就是本题的难点了。假设 $x$ 的出现次数小于 $\sqrt{n}$ ，$y$ 的出现次数大于 $\sqrt{n}$ 。这个时候可以发现，对于 $y$ 的查询是 $O(1)$ 的，太舒服了，能不能跟修改达成某种平衡呢？

  具体的，考虑对于每一个出现次数大于 $\sqrt{n}$ 的颜色维护一个临时集合，在求答案的时候，多考虑一个临时集合即可。然后每一次将 $x$ 并到临时集合中，如果临时集合的大小大于 $\sqrt{n}$，就重构 $y$ 的距离数组，容易重构次数为 $O(\sqrt{n})$ 级别，因此这一部分复杂度是对的。

然后就做完了。

---

关于实现：

• 细节较多，码量中等，中等卡常。

• 注意一下因为常数原因块大小应该比 $\sqrt{n}$ 稍大，我的块大小是 $10^3$ 。

• 重构的时候需要查询原序列，这里比较粗暴的直接用并查集维护了 = =

const int N=1e5+5;
const int SqrtN=1e2+5;

const int w=SqrtN-1;
int n,m,sqrtn,last_ans,a[N];

// {{{ Data_Struct_Block

bool live[N];
int rt[N],fa[N],col[N];
int top,tmp_las,id[N],pot[N],idsta[SqrtN],dis[SqrtN][N];
std::vector <int> sta[N],tmp_sort;

int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}

inline void update_dis(int &_id,const int &i) {
    if(!_id) _id=idsta[top--],memset(dis[_id],64,sizeof(dis[_id]));
    tmp_las=-inf;
    lep(j,1,n) {if(col[find(j)]==i) tmp_las=j; chkmin(dis[_id][pot[col[find(j)]]],j-tmp_las);}
    tmp_las=inf;
    rep(j,n,1) {if(col[find(j)]==i) tmp_las=j; chkmin(dis[_id][pot[col[find(j)]]],tmp_las-j);}
}

inline void merge_sort(std::vector <int> &sx,std::vector <int> &sy) {
    int ix=0,iy=0; const int limx=sx.size()-1,limy=sy.size()-1;
    while(ix<=limx&&iy<=limy) tmp_sort.pb(sx[ix]>sy[iy]?sy[iy++]:sx[ix++]);
    while(ix<=limx) tmp_sort.pb(sx[ix++]);
    while(iy<=limy) tmp_sort.pb(sy[iy++]);
    return sy=tmp_sort,tmp_sort.clear(),sx.clear();
}
inline void merge(int x,int y) {
    if(x==y||!live[x]) return ;
    if(!live[y]&&live[x])
        return swap(live[x],live[y]),swap(pot[x],pot[y]),col[rt[y]=rt[x]]=y,rt[x]=0,void();
    if(!id[pot[y]]) swap(pot[x],pot[y]);

    const int &px=pot[x],&py=pot[y];
    live[x]=0,fa[rt[x]]=rt[y],col[rt[x]]=0,rt[x]=0;

    if(id[py]&&id[px]) {
        lep(i,1,n) chkmin(dis[id[py]][i],dis[id[px]][i]);
        idsta[++top]=id[px],id[px]=0;
    }
    merge_sort(sta[px],sta[py]);
    if(sta[py].size()>sqrtn) update_dis(id[py],y),sta[py].clear();
    lep(i,1,w) chkmin(dis[i][py],dis[i][px]),dis[i][px]=inf;
}

inline int calc(const std::vector <int> &sx,const std::vector <int> &sy) {
    int ans=inf,ix=0,iy=0;
    const int limx=sx.size()-1,limy=sy.size()-1;
    while(ix<=limx&&iy<=limy) (sx[ix]<sy[iy])?chkmin(ans,sy[iy]-sx[ix++]):chkmin(ans,sx[ix]-sy[iy++]);
    return ans;
}
inline void query(int x,int y) {
    if(!live[x]||!live[y]) return last_ans=0,puts("Ikaros"),void();
    if(x==y) return printf("%d\n",last_ans=0),void();
    x=pot[x],y=pot[y];
    int res=calc(sta[x],sta[y]);
    printf("%d\n",last_ans=min(res,min(dis[id[x]][y],dis[id[y]][x])));
}

// }}}

int op,x,y;
int main() {
    IN(n,m),sqrtn=1000;
    lep(i,1,SqrtN-1) idsta[++top]=i;
    memset(dis[0],64,sizeof(dis[0]));

    lep(i,1,n) live[i]=false,pot[i]=i;
    lep(i,1,n) IN(a[i]),live[a[i]]=true,sta[a[i]].pb(i);
    lep(i,1,n) {if(!rt[a[i]]) col[rt[a[i]]=i]=a[i]; fa[i]=rt[a[i]];}
    lep(i,1,n) if(sta[i].size()>sqrtn) update_dis(id[i],i),sta[i].clear();

    while(m--) {
        IN(op,x,y),x^=last_ans,y^=last_ans;
        if(op==1) merge(x,y);
        if(op==2) query(x,y);
    }    
    return 0;
}